#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
string Deletzero(string& s)
{
	string s2 = "";
	bool flag = false;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '1' || flag)
		{
			s2 = s2 + s[i];
			flag = true;
		}
	}
	if (s2.size() == 0) { return "0"; }
	else { return s2; }
}
string change(char c)
{
	int tmp = (int)(c)-48;
	//cout<< tmp<<endl;
	string s="";
	//
	for (int i = 0; i < 4; i++)
	{
		if (1 & tmp)
		{
			s = '1'+s;
			//flag = true;
		}
		else{ s = '0'+s; }
		tmp = tmp >> 1;
	}
	//cout << s << endl;
	string s2 = Deletzero(s);
	if (s2.size() == 0) { return "0"; }
	else { return s2; }
}

string Fa(string&s)
{
	string re="";
	//每一个字符转成正数
	for (int i = 0; i < s.size(); i++)
	{
		re = re + change(s[i]);
		//cout << change(s[i]) << endl;
	}
	return re;
}
void fanzhuan(string&s)
{
	int i = 0, j = s.size() - 1;
	while (i < j)
	{
		swap(s[i],s[j]);
		
		i++; j--;
	}
	//delet
	s = Deletzero(s);
}
string Fc(string s)
{
	stack<char>st;
	if (s.size() == 0) { return "0"; }
	else
	{
		st.push(s[0]);
	}
	for (int i = 1; i < s.size(); i++)
	{
		while (st.top() != s[i])
		{
			st.push(s[i]);
		}
	}
	string s2 = "";
	while (!st.empty())
	{
		s2 = s2 + st.top();
		st.pop();
	}
	return s2;
}
int main()
{
	int t;
	string s;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> s;
		string tmp = Fa(s);
		fanzhuan(tmp);
		tmp = Fc(tmp);
		cout << tmp;
		
	}
}